package com.zh.note.leetcode.graph;

/**
 * @Author: zhanghuan
 * @date: 2023/9/13 11:21
 * @description: create it
 */
public class LC_200_numIslands {

    public static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int numIslands(char[][] grid) {
        int res = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j] == false && grid[i][j] == '1') {
                    res++; //遇到没访问过的陆地，+1
                    dfs(grid, i, j, visited);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int x, int y, boolean[][] visited) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] == true || grid[x][y] == '0') {
            return;
        }
        visited[x][y] = true; //将与其链接的陆地都标记上
        for (int i = 0; i < dir.length; i++) {
            int newX = x + dir[i][0];
            int newY = y + dir[i][1];
            dfs(grid, newX, newY, visited);
        }

    }
}
